1. Technical Field
The present disclosure relates to caches used in memory systems and more specifically to garbage collection in caches.
2. Related Art
A cache stores a copy of source data maintained in a source memory, and is located closer to a component (e.g., processor) seeking to access the data for reasons such as higher throughput performance. The component is provided the ability to access a data item of interest from the cache if such data item is present in the cache, and the data is retrieved from the source memory if not present in the cache, as is well known in the relevant arts. Caches find use in diverse areas to speed up accesses to data such as that may be stored as a source data in a random access memory (RAM), that may be stored in a database (secondary storage based), etc. Thus, a cache contains multiple entries in a memory, with each entry storing a copy (“cache item”) of a data item that is also stored in a corresponding source memory.
Garbage collection refers to identifying suitable entry or entries for storing new data items in a cache. The need for such identification typically stems from the limited number of entries in a cache. In one approach, garbage collection is performed periodically to identify a set of entries that contain data items unlikely to be accessed again, and these set of entries are thereafter used to store new data items. In addition or in the alternative, when a new entry is available for storing and there are no unused entries (i.e., no entries with not-valid data item stored) garbage collection is initiated to identify one or more suitable entries for storing data items (including the available data item).
Garbage collection requires various resources such as computational power and memory, the magnitude of which may be characterized as (computational/memory requirements) complexity of the corresponding approach. Several prior approaches perform garbage collection based on parameters such as idle time of an entry (i.e., duration the entry has not been accessed in cache), the hit frequency (i.e., the number of times the entry was accessed in a pre-specified duration). Some of these approaches require sorting of the parameter values and/or complex data structures to determine the suitable entries for replacement. Such approaches would accordingly be characterized by correspondingly higher computational and/or memory complexity.
It is often desirable that garbage collection be performed with reduced complexity in terms of memory and/or computational requirements.
In the drawings, like reference numbers generally indicate identical, functionally similar, and/or structurally similar elements. The drawing in which an element first appears is indicated by the leftmost digit(s) in the corresponding reference number.